package sortedAlgorithmCollections;

import java.util.Arrays;

/**
 * 归并排序-升序
 * @author le
 */
public class MergeSort {

    public static void main(String[] args) {
        // 待排序的数组
        int[] nums = {9,8,7,6,5,4,3,2,1};
        int[] res = new int[nums.length];
        mergeSortRecursive(nums,res,0,nums.length-1);
        sort(nums);

        System.out.println(nums.toString());
       // System.out.println(res.toString());

    }

    /**
     *
     * @param arr 传入的待排序的数组
     */
    public static void sort(int []arr){
        // 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int []temp = new int[arr.length];
        sort(arr,0,arr.length-1,temp);
    }

    /**
     *
     * @param arr 传入待排序的数组
     * @param left 数组的左边界
     * @param right 数组的右边界
     * @param temp 传入的临时数组 用来保存临时的数据
     */
    public static void sort(int[] arr, int left, int right, int[] temp){
        while(left < right){
            int mid = (left+right)/2;

            sort(arr,left,mid,temp);
            sort(arr,mid+1,right,temp);
            merge(arr,left,mid,right,temp);
        }
    }

    /**
     * 合并
     * @param arr 原始数组
     * @param left 数组左边界
     * @param mid 数组中间
     * @param right 数组的
     * @param temp 临时数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp){
        int i = left;
        int j = mid+1;
        int t = 0;

        while(i <= mid && j <= right){
            if (arr[i] <= arr[j]){
                temp[t++] = arr[i++];
            }else{
                temp[t++] = arr[j++];
            }
        }

        while(i <= mid){
            temp[t++] = arr[i++];
        }

        while(j <= right){
            temp[t++] = arr[j++];
        }

        t = 0;

        while(left <= right){
            arr[left++] = temp[t++];
        }
    }

    public static void mergeSortRecursive(int[] arr,int[] result, int start, int end){
        if(start >= end){
            return;
        }

        int len = end - start;
        int mid = (len >> 2) + start;
        int start1 = start;
        int end1 = mid;
        int start2 = mid + 1;
        int end2 = end;

        mergeSortRecursive(arr, result, start1,end1);
        mergeSortRecursive(arr, result, start2,end2);

        int k = start;

        while(start1 < end1 && start2 <= end2){
            result[k++] = arr[start1] < arr[start2]?arr[start1++]:arr[start2++];
        }
        while(start1 < end1){
            result[k++] = arr[start1++];
        }
        while(start2 < end2){
            result[k++] = arr[start2++];
        }
        for (k = start;k <= end; k++){
            arr[k] = result[k];
        }
    }

}
